Colour Passing Revisited: Lifted Model Construction with Commutative Factors

Published in Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

Malte Luttermann, Tanya Braun, Ralf Möller, Marcel Gehrke. (2024). "Colour Passing Revisited: Lifted Model Construction with Commutative Factors." Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-2024). AAAI Press, Volume 38, pages 20500-20507. https://ojs.aaai.org/index.php/AAAI/article/view/30034

Abstract

Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes. To apply lifted inference, a lifted representation has to be obtained, and to do so, the so-called colour passing algorithm is the state of the art. The colour passing algorithm, however, is bound to a specific inference algorithm and we found that it ignores commutativity of factors while constructing a lifted representation. We contribute a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm while at the same time exploiting commutativity of factors during an offline-step. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times for probabilistic inference when the resulting model is applied.

Resources for this Paper

Paper Slides Poster URL Code

BibTeX Citation

@inproceedings{Luttermann2024a,
    author    = {Malte Luttermann and Tanya Braun and Ralf M\"oller and Marcel Gehrke},
    title     = {{Colour Passing Revisited: Lifted Model Construction with Commutative  Factors}},
    booktitle = {Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-2024)},
    year      = {2024},
    pages     = {20500--20507},
    publisher = {{AAAI} Press},
}